#include "..\CookHeader.h"

int maxWeight = 7;		// 賶 ִ 
int rowCount = 4;		//  
Array <int> weight = { 0, 6, 4, 3, 5 };		//  (0, ݱ, , , )
Array <int> money = { 0, 13, 8, 6, 12 };	//  (0, ݱ, , , )

int knapsack() {
	println("## ޸̼ 迭 ##");

	Array <Array <int>> memoAry;
	memoAry = emptyArray2(rowCount + 1, maxWeight + 1);	//  迭 غ

	for (int row = 1; row < rowCount + 1; row++) {
		print(to_string(row) + " -->");				// 1 ~ 4(4ȸ)
		for (int col = 1; col < maxWeight + 1; col++) {	// 1col KG ~ 7col KG
			if (weight[row] > col) {		//  ԰  ũ ==  濡  
				memoAry[row][col] = memoAry[row - 1][col];
			} else {						//  濡 
				int value1 = money[row] + memoAry[row - 1][col - weight[row]];
				int value2 = memoAry[row - 1][col];
				memoAry[row][col] = max(value1, value2);
			}
			printf("%3d", memoAry[row][col]);
		}
		println("");
	}
	return memoAry[rowCount][maxWeight];
}

int main() {
	int maxValue = knapsack();
	println("\n賶   ִ  ִ  -->" + to_string(maxValue) + " ");
}